<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Free CSS Templates
http://www.freecsstemplates.org
Released for free under a Creative Commons Attribution 2.5 License
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>CSC560 Design and Analysis of Real-Time Systems</title>
<meta name="keywords" content="CSC560" />
<meta name="description" content="CSC560" />
<link href="../default.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="wrapper">
	<div id="header">
		<h1>CSC560</h1>
		<h2>Design and Analysis of Real-Time Systems</h2>
		<ul>
			<li class="first"> <a href="../index.html" accesskey="1" title="">Home</a> </li>
			<li> <a href="../project1/index.html" accesskey="2" title="">Project 1</a>	</li>
			<li> <a href="../project2/index.html" accesskey="3" title="">Project 2</a> </li>
			<li> <a href="index.html" accesskey="4" title=""><b>Project 3</b></a> </li>
			<li> <a href="#" accesskey="4" title="">Project 4</a> </li>
			<li> <a href="#" accesskey="4" title="">Project 5</a> </li>
		</ul>
	</div>
</div>
<div id="content">
	<div id="colOne">
		<h2>Bounded Round Robin</h2>
		<p>
			
		</p>
		<h3>Requirements</h3>
		<p>
			We have implemented the following requirements:
			<table cellpadding="0" cellspacing="0" border="0">
		<thead>
			<tr>
				<th><h3>Feature Name</h3></th>
				<th><h3>Description</h3></th>
			</tr>
		</thead>
		<tbody>
			<tr>
				<td>Creation</td>
				<td>When a BRR is created, it is assigned a quantum of "n".</td>
			</tr>
			<tr>
				<td>Task_Next()</td>
				<td>A BRR may yield before its quantum has expired, by calling Task_Next().
					If it calls Task_Next(), it is rescheduled with its initial quantum "n" created.</td>
			</tr>
			<tr>
				<td>Task_Next_Quantum()</td>
				<td>A BRR may yield before its quantum has expired, by calling Task_Next_Quantum(n).
					If it calls Task_Next_Quantum(n), it is rescheduled with a new quantum "n".</td>
			</tr>
			<tr>
				<td>Scheduling</td>
				<td>
					A BRR task with quantum of "m" (m>=1) must fit into the next IDLE time before
					the next PERIODIC task. Otherwise, it is rescheduled, e.g.: put back at the end
					of the queue. Our implementation will look for the next BRR task that fits into the
					IDLE time available. If no BRR task satisfies this requirement, the idle_task is assigned.
				</td>
			</tr>
			<tr>
				<td>Pre-emption</td>
				<td>
					A BRR task may be interrupted by a SYSTEM level task, and will not execute for its
					specified quantum. When a BRR is preempted, it is assumed that it has consumed all its
					quantum.
				</td>
			</tr>
			<tr>
				<td>Quantum of 0</td>
				<td>
					A BRR task may be assigned a quantum of 0. In this case, it is treated as a FCFS, and run
					to completion.
				</td>
			</tr>
		</tbody>
  </table>
		</p>
		<h3>Development Process</h3>
		<p>
			1. Data Structures modified:<br><br>
			We have added fields to task_descriptor_t in kernel.h to handle the initial and remaining quantum.
			We have inserted two fields: initial_quantum and remaining_quantum.
		</p>
		
		<p>
			2. Creating a Task<br><br>
			When we create a BRR task, the first lines of code we introduced is a check for illegal quantum.
			We have modified kernel_create_task() to introduce this check. 
			An illegal quantum is a quantum that is either smaller than 0 or greater than MAXQUANTUM.
			Next, we assign the quantum passed as a parameter to the fields initial quantum 
			and remaining quantum of the structure task_descriptor_t and we add the BRR task on its round robin queue. 
			Another important case to consider is when a system or periodic task is created. In both cases, if the 
			current task is BRR, it must be pre-empted and its states put back to READY, so that the system or periodic
			task can execute. In this case, we will also reset the remaining quantum back to its initial quantum. 
		</p>
		
		<p>
			3. Task_Next()<br><br>
			We have modified RTOS so that when a BRR task calls Task_Next(), it resets the remaining quantum to its initial quantum.
			Therefore, the next time the BRR task will run, its remaining quantum is equal to its initial quantum.
		</p>
		
		<p>
			4. Task_Next_Quantum()<br><br>
			We have modified RTOS so that when a BRR task calls Task_Next_Quantum(), for all the following times
			this task runs, it is given that quantum. Therefore, calling Task_Next_Quantum() will modify 
			both the initial quantum and the remaining quantum. Another possible way of 
			implementation is to only give the new quantum for the next time it runs.
		</p>
		<p>
			5. Scheduling<br><br>
			Scheduling is divided into 3 parts:
			1. Execution Priority
			The RTOS code structure already takes care of scheduling a system level or periodic level task before
			scheduling a BRR level task. Indeed, if the system level queue is not empty we dequeue a task to execute from the system queue. 
			If the system queue is empty, but the periodic queue is not, then we dequeue a task to execute from the
			periodic queue. Finally, if the BRR queue is not empty, we will schedule the next 
			BRR task depending on two scenarios:
			1. If the current task is not running and is of periodic level
			In this case, we must find the next appropriate BRR task to run. Our algorithm calculates the maximum time a BRR
			could run. There are two sub cases to consider. First, the maximum time is the time available after the periodic task 
			has finished executing and before the next periodic task executes. The second case is the same, except that if the 
			next periodic task is the IDLE task, then we must add the IDLE time to the time after which the periodic task has finished
			executing, and before the next periodc task executes. This will possibly allow a BRR with a larger quantum to execute. Then,
			we loop over the brr queue and find the next task that has a quantum smaller or equal to the time calculated. If we reach the
			end of the queue and no task is found to satisfy the requirement, then we set the idle_task as the current task.
			2. If the current task is a system level task
			In this case, we verify if there is another periodic task that is scheduled. If so, we do as in the first part. Otherwise, 
			we simply select the next BRR task on the queue.  
		</p>
		<p>
			6. Pre-emption<br><br>
			If a system task needs to preempt a BRR task, then RTOS will put back the BRR task to the end of the queue, and reset its
			remaining quantum to its initial value. In the case that a BRR with quantum of 0 runs, it is possible that a periodic task needs
			to preempt the BRR task. In this case, it will behave exactly as in the case of a system task. It is important to note that there
			should not be any periodic task preempting a BRR task otherwise, since our RTOS should have been careful enough not to schedule
			any BRR task with a quantum longer than the elapsed time between the time a periodic task finishes and the beginning of the next periodic
			task.
		</p>
		<p>
			7. Quantum of 0<br><br>
			It is also important to note that our scheduling policy will be different if a BRR task has a quantum of 0. In this case, when we are iterating
			over the BRR queue and we find a task that has a quantum of 0, we will simply dequeue this task and let it execute. This does not mean that 
			the task will be able to execute to completion, it might be pre-empted by a system or periodic task. It only shows that our scheduling policy
			is a best-effort one, meaning that at a particular point in time we try to fit the best next task available.
		</p>
		
	</div>
	<div id="colTwo">
		<h3>Project Sections</h3>
		<ul>
			<li class="first"><a href="part1_brr.html"><b>Bounded Round Robin</b></a></li>
			<li><a href="part2_mutex.html">Timed Mutex</a></li>
			<li><a href="part3_test_cases.html">Test Cases</a></li>
			<li><a href="part4_logic_analyzer.html">Logic Analyzer</a></li>
			<li><a href="doxygen/html/index.html">Doxygen</a></li>
			<li><a href="http://code.google.com/p/wireless-roomba">Google Code</a></li>
		</ul>
	</div>
</div>
<div id="footer">
	<p>
		@ 2009. All Rights Reserved. Design by 
		<a href="http://www.freecsstemplates.org/">Free CSS Templates</a>.
	</p>
</div>
</body>
</html>
